`
https://leetcode.cn/problems/kth-smallest-element-in-a-sorted-matrix/
`

/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function (matrix, k) {
  const n = matrix.length

  // 第 k 小等价于最小的 x ，序列中 <= x 的至少有 k 个
  // 给定 x ，计算矩阵中 <= x 的个数 cnt 是否满足 cnt >= k
  const check = (x) => {
    let cnt = 0
    for (const arr of matrix) {
      // 找到最后一个 <= x 的位置，下标 + 1 即为个数
      cnt += _.sortedIndex(arr, x + 1)
      if (cnt >= k) return true
    }
    return false
  }

  let left = Math.min(...matrix.map((arr) => arr[0])) - 1
  let right = Math.max(...matrix.map((arr) => arr.at(-1))) + 1
  while (left + 1 < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (check(mid)) {
      right = mid
    } else {
      left = mid
    }
  }
  return right
};